/**
 * Created With IntelliJ IDEA
 * Description:牛客网:JD1 年终奖
 * <a href="https://www.nowcoder.com/practice/72a99e28381a407991f2c96d8cb238ab?tpId=134&tqId=33854&ru=/exam/oj">...</a>
 * User: DELL
 * Data: 2023-04-16
 * Time: 11:34
 */
//本题有动态规划和递归两个方法，均较为简单，这里是动态规划的方法
public class Bonus {
    public int getMost(int[][] board) {
        //题目中已经规定这是一个 6*6 的棋盘
        int[][] bp = new int[6][6];
        //初始化 bp 的第一行和第一列
        bp[0][0] = board[0][0];
        for (int i = 1; i < 6; i++) {
            bp[i][0] = bp[i-1][0] + board[i][0];
            bp[0][i] = bp[0][i-1] + board[0][i];
        }
        //动态规划
        for (int i = 1; i < 6; i++) {
            for (int j = 1; j < 6; j++) {
                bp[i][j] = Math.max(bp[i-1][j],bp[i][j-1]) + board[i][j];
            }
        }
        return bp[5][5];
    }
}